package leetcode.editor.day;

// 1422. 分割字符串的最大得分
// https://leetcode.cn/problems/maximum-score-after-splitting-a-string/
class MaximumScoreAfterSplittingAString {
    public static void main(String[] args) {
        Solution solution = new MaximumScoreAfterSplittingAString().new Solution();
        solution.maxScore("011101");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 暴力
        /*public int maxScore(String s) {
            int res = 0;
            for (int i = 1; i < s.length(); i++) {
                int count = 0;
                String left = s.substring(0, i);
                String right = s.substring(i);

                for (int j = 0; j < left.length(); j++) {
                    if (left.charAt(j) == '0') count++;
                }

                for (int j = 0; j < right.length(); j++) {
                    if (right.charAt(j) == '1') count++;
                }

                res = Math.max(res, count);
            }

            return res;
        }*/

        public int maxScore(String s) {
            // 先统计1的个数
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '1') count++;
            }

            // 记录 s[i] 左边（包括s[i]）的字符 0 1 的个数
            int ans = 0, one = 0, zero = 0;
            for (int i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) == '0') zero++;
                else one++;
                ans = Math.max(ans, zero + count - one);
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
